// https://leetcode.cn/problems/search-a-2d-matrix-ii/description/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 从矩阵右上角开始搜索目标值
// 2. 利用矩阵行列有序特性进行剪枝
// 3. 当前值大于目标时左移，小于目标时下移
// 4. 逐步缩小搜索范围直至找到或越界
// 5. 时间复杂度：O(m+n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) 
    {
        int m = matrix.size(), n = matrix[0].size();

        int x = 0, y = n - 1;
        while (x >= 0 && x < m && y >= 0 && y < n)
        {
            if (matrix[x][y] == target)
            {
                return true;
            }
            else if (matrix[x][y] > target)
            {
                y--;
            }
            else
            {
                x++;
            }
        }

        return false;
    }
};

int main()
{
    vector<vector<int>> matrix1 = {{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
    vector<vector<int>> matrix2 = {{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
    int target1 = 5, target2 = 20;

    Solution sol;

    cout << (sol.searchMatrix(matrix1, target1) == 1 ? "True" : "False") << endl;
    cout << (sol.searchMatrix(matrix2, target2) == 1 ? "True" : "False") << endl;

    return 0;
}